package 高频题;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class 单词拆分_139 {
    /*
     动态规划算法，dp[i]表示s前i个字符能否拆分
     转移方程：dp[j] = dp[i] && check(s[i+1, j]);
     check(s[i+1, j])就是判断i+1到j这一段字符是否能够拆分
     其实，调整遍历顺序，这等价于s[i+1, j]是否是wordDict中的元素
     这个举个例子就很容易理解。
     假如wordDict=["apple", "pen", "code"],s = "applepencode";
     dp[8] = dp[5] + check("pen")
     翻译一下：前八位能否拆分取决于前五位能否拆分，加上五到八位是否属于字典
     （注意：i的顺序是从j-1 -> 0哦~
 */
    public HashMap<String, Boolean> hash = new HashMap<>();

    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];

        //方便check，构建一个哈希表
        for (String word : wordDict) {
            hash.put(word, true);
        }

        //初始化
        dp[0] = true;

        //遍历
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                dp[i] = dp[j] && check(s.substring(j, i));
                if (dp[i]) {
                    break;
                }
            }
        }

        return dp[s.length()];
    }

    public boolean check(String s) {
        return hash.getOrDefault(s, false);
    }
}
